"""
题目：将两个升序排列的单链表合并为一个新的升序单链表。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_two_lists(l1, l2):
    # 创建哑节点，简化边界处理
    dummy = ListNode(0)
    current = dummy  # 当前节点指针，初始指向哑节点

    # 当两个链表都不为空时
    while l1 and l2:
        # 比较两个链表当前节点的值
        if l1.val < l2.val:
            current.next = l1  # 取l1的节点
            l1 = l1.next  # 移动l1指针
        else:
            current.next = l2  # 取l2的节点
            l2 = l2.next  # 移动l2指针
        current = current.next  # 移动当前节点指针

    # 处理剩余节点（如果有）
    current.next = l1 if l1 else l2

    return dummy.next  # 返回合并后的头节点


# 辅助函数（复用）
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
l1 = create_linked_list([1, 3, 5])
l2 = create_linked_list([2, 4, 6])
merged_head = merge_two_lists(l1, l2)
print(traverse_linked_list(merged_head))  # 输出: [1, 2, 3, 4, 5, 6]
